﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LostLib.Algorithms
{
	[Serializable]
	public class Diff<E>
		where E: IEquatable<E>
	{
		#region Algorithms
		public static IEnumerable<E> LongestCommonSubsequence<T>(T a, T b)
			where T: IList<E>
		{
			int[,] max_len = new int[a.Count + 1, b.Count + 1];

			for (int i = (int)a.Count - 1; i >= 0; i--)
			{
				for (int j = (int)b.Count - 1; j >= 0; j--)
				{
					if (a[i].Equals(b[j]))
					{
						max_len[i, j] = 1 + max_len[i + 1, j + 1];
					} else
					{
						max_len[i, j] = Math.Max(max_len[i + 1, j], max_len[i, j + 1]);
					}
				}
			}
			
			List<T> result = new List<T>();
			for (int i = 0, j = 0; max_len[i, j] != 0 && i < a.Count && j < b.Count; )
			{
				if (a[i].Equals(b[j]))
				{
					yield return a[i];
					i++;
					j++;
				} else
				{
					if (max_len[i, j] == max_len[i + 1, j])
						i++;
					else
						j++;
				}
			}
		}

		public static IEnumerable<Diff<E>> GetDiff<T>(T original, T @new)
			where T:IList<E>
		{
			var lcs = LongestCommonSubsequence(original, @new).ToArray();

			int apos = 0;
			int lcspos = 0;
			int bpos = 0;

			while (apos < original.Count)
			{
				if (lcspos >= lcs.Length)
				{
					var lastRemove = Remove(apos);
					lastRemove.Count = original.Count - lastRemove.Position;
					yield return lastRemove;
					break;
				}

				var delete = Remove(apos);
				while (apos < original.Count && !original[apos].Equals(lcs[lcspos]))
				{
					apos++;
				}
				if (apos != delete.Position)
				{
					delete.Count = apos - delete.Position;
					yield return delete;
				}

				var insert = Insert(apos);

				while (bpos < @new.Count && !@new[bpos].Equals(lcs[lcspos]))
				{
					insert.Data.Add(@new[bpos]);
					bpos++;
				}
				if (insert.Data.Count > 0)
					yield return insert;

				while (apos < original.Count && original[apos].Equals(@new[bpos]))
				{
					apos++;
					bpos++;
					lcspos++;
				}
			}

			var lastInsert = Insert(apos);
			while(bpos < @new.Count)
			{
				lastInsert.Data.Add(@new[bpos]);
				bpos++;
			}
			if (lastInsert.Data.Count > 0)
				yield return lastInsert;
		}
		#endregion

		#region Data Structure
		public int Position { get; set; }
		public int Count { get; set; }
		public List<E> Data { get; set; }
		public bool IsInsert { get; set; }

		public override string ToString()
		{
			if (IsInsert)
			{
				var result = new StringBuilder();
				result.Append("+ ");
				result.Append(Position);
				result.Append('\n');
				foreach (var item in Data)
					result.AppendLine(item.ToString());

				return result.ToString();
			} else
			{
				return string.Format("- {0}, {1}\n", Position, Count);
			}
		}
		#endregion Data Structure

		#region Creating
		public static Diff<E> Remove(int pos)
		{
			return new Diff<E> {
				IsInsert = false,
				Position = pos,
			};
		}
		public static Diff<E> Insert(int pos)
		{
			return new Diff<E> {
				IsInsert = true,
				Data = new List<E>(),
				Position = pos
			};
		}
		#endregion Creating
	}

	public static class DiffExtensions
	{
		public static List<E> Apply<T, E>(this IEnumerable<Diff<E>> diffs, T source)
			where T: IList<E>
			where E: IEquatable<E>
		{
			int pos = 0;

			var result = new List<E>(source.Count);

			foreach (var diff in diffs)
			{
				while (diff.Position > pos)
				{
					result.Add(source[pos]);
					pos++;
				}

				if (diff.IsInsert)
				{
					result.AddRange(diff.Data);
				} else
				{
					pos += diff.Count;
				}
			}

			while (pos < source.Count)
				result.Add(source[pos++]);

			return result;
		}
	}
}
